package com.jzoffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class FindValuePath {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(8);
        TreeNode t4 = new TreeNode(7);
        TreeNode t5 = new TreeNode(9);
        TreeNode t6 = new TreeNode(12);
        TreeNode t7 = new TreeNode(3);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
        t3.right = t7;
        ArrayList<ArrayList<Integer>> arrayLists = FindPath(t1, 16);
        System.out.println(Arrays.toString(arrayLists.toArray()));

    }

    // 二叉树中和为某一个值的路径
    public  static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target){
        ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
        if(root == null){
            return paths;
        }
        Stack<Integer> stack = new Stack<>();
        subFindPath(root,target,paths,stack);
        return paths;

    }

    private static void subFindPath(TreeNode root, int target,ArrayList<ArrayList<Integer>> paths,Stack<Integer> stack){
        if(root == null){
            return;
        }
        // 叶结点
        if(root.left == null && root.right == null){
            if(root.val == target){
                ArrayList<Integer> path = new ArrayList<>();
                for(int num:stack){
                    path.add(num);
                }
                path.add(root.val);
                paths.add(path);
            }
        }else{
            // 非叶结点
            stack.push(root.val);
            subFindPath(root.left,target - root.val,paths,stack);
            subFindPath(root.right,target - root.val,paths,stack);
            stack.pop();

        }
    }
}
